1. Technical Field
The invention relates generally to optimization techniques. More particularly, the invention relates to a computer implemented method and apparatus for providing an optimal solution for a large consumer decision.
2. Description of the Prior Art
A large consumer decision is characterized by a decision made for millions of accounts with one or more global constraints. The inclusion of the global constraints means that the decisions for all accounts must be examined all together. Such problem in academics has been labeled an NP-hard problem (it is formulated as a 0,1-linear program), because the combinations exponentially rise based on the number of accounts and the number of decision alternatives for each account. A typical solution to the problem can be described with reference to FIG. 1, a schematic block diagram showing components of a solver for a consumer decision according to the prior art. Samples or segments of account 2 data are provided as input into a calculator 4 which consists of user defined scoring functions and system functions. The output of the calculator is used to construct the objective, constraints of the 0,1-linear program of the consumer decision model. The relaxation of the linear program is the input to a linear program (LP) solver 8. The LP solver outputs a solution which might contains fractions 10. It should be appreciated that some custom solvers enforce a limitation on the number of variables or type of constraints allowed.
This problem has been around for the last ten years, i.e. since the consumer-marketing sector started to look at using optimization algorithms to assist with decisions on what to offer consumers. The credit card industry, for example, has been a leader in applying these algorithms.
The current approach in the industry uses sampling and segmentation techniques when applying optimization algorithms to large scale consumer decisions that include global constraints. In sampling techniques, the solution depends on the quality of the samples. In segmenting techniques, the solution depends on the quality of the segments. Such sampling and segmentation techniques are used due to limitations of existing optimization algorithms and computer memory. Most algorithms require the entire problem to be loaded into memory. These decision problems do not fit into a 32 bit address space. On occasion custom code has been written that may reduce the problem in other ways, such as only requiring one global constraint and narrowing the solution to solve only one specific type of decision. Another approach includes using 64 bit computers. However, such computers are expensive and the solvers are either new or inexperienced.
It should be appreciated that all such approaches achieve varying degrees of success, depending on the experience of the people applying the approaches and the applicability of the sampling, segmentation, and/or problem reduction techniques. None are fully acceptable for today's projects.
Y. Galperin, V. Fishman, and L. Gibiansky, Method for Optimizing Net Present Value of a Cross-Selling Marketing Campaign, WO0111522 (published Feb. 15, 2001) discuss an iterative algorithm to the problem of multidimensional optimization of cross-selling. The techniques discussed therein describe a solution by supplying a non-linear mathematical formulation, the non-linearity being due to introducing the Lagrange multipliers, to the traditional linear multidimensional problem desired to be solved when offering a large number of promotions M to a very large set of prospective customers N. Such process consists of randomly selecting a statistically significant sample of a prospect list, calculating the value of a utility function for each pair of an offer and selected prospects, reducing the original linear multidimensional problem to a smaller problem (still linear) with a feasible number of dimensions, solving the smaller problem for the selected sample numerically with the desired tolerance using an iterative algorithm, and using the results to calculate a set of offers in one pass for the full prospect list. It should be appreciated that Galperin, et al only use a sample of data, not all of the data, and do not guarantee the optimality, just a solution.
It would be advantageous to solve very large optimization problems at the account level.
It would be advantageous to provide an algorithm that takes advantage of the structure for the consumer decisions and the criteria used to evaluate the decisions, and, such that while taking all data into consideration, the algorithm formulates a much smaller problem to feed a solver.
It would be advantageous to provide a method and apparatus where the size of the problem fed to a solver can be configured.
It would be further advantageous to provide an algorithm that is able to find the global solution to the problem initially posed, even with the smaller problem fed to the solver.
It would be advantageous to provide a solver that removes the dependencies on third parties.